package Leetcode.Dichotomy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @Author: kirito
 * @Date: 2024/4/6 13:51
 * @Description:
 *可以到达的最远建筑
 * 给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
 *
 * 你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
 *
 * 当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：
 *
 * 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
 * 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
 * 如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
 *
 *
 * 示例 1：
 *
 *
 * 输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
 * 输出：4
 * 解释：从建筑物 0 出发，你可以按此方案完成旅程：
 * - 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
 * - 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
 * - 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
 * - 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
 * 无法越过建筑物 4 ，因为没有更多砖块或梯子。
 * 示例 2：
 *
 * 输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
 * 输出：7
 * 示例 3：
 *
 * 输入：heights = [14,3,19,3], bricks = 17, ladders = 0
 * 输出：3
 *
 *
 * 提示：
 *
 * 1 <= heights.length <= 105
 * 1 <= heights[i] <= 106
 * 0 <= bricks <= 109
 * 0 <= ladders <= heights.length
 */

public class furthestBuilding {
    /**
     * 优先队列加贪心
     * 优先使用梯子，梯子不够时选取差值最小的出堆改用砖头。(小根堆)
     * 优先使用砖头，砖头不够时选取消耗最大的出堆改用梯子。(大根堆)
     * @param heights
     * @param bricks
     * @param ladders
     * @return
     */
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int n = heights.length;
        // 由于我们需要维护最大的 l 个值，因此使用小根堆
        PriorityQueue<Integer> ladderAllocations = new PriorityQueue<>();
        // 需要使用砖块的 delta h 的和
        int sumH = 0;
        for (int i = 1; i < n; ++i) {
            int deltaH = heights[i] - heights[i - 1];
            if (deltaH > 0) {
                ladderAllocations.add(deltaH);
                // 如果优先队列已满，需要拿出一个其中的最小值，改为使用砖块
                if (ladderAllocations.size() > ladders) {
                    sumH += ladderAllocations.poll();
                }
                if (sumH > bricks) {
                    return i - 1;
                }
            }
        }
        return n - 1;
    }

    /**
     * 二分
     * @param heights
     * @param bricks
     * @param ladders
     * @return
     */
    public int furthestBuilding2(int[] heights, int bricks, int ladders) {
        int l = ladders, r = heights.length - 1;
        while(l <= r) {
            int mid = l + r >>> 1;
            if(check(heights, bricks, ladders, mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }
    private boolean check(int[] heights, int bricks, int ladders, int n) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            if(heights[i + 1] - heights[i] > 0) {
                list.add(heights[i + 1] - heights[i]);
            }
        }
        Collections.sort(list);
        int sum = 0;
        for(int i = 0; i < list.size() - ladders; i ++) {
            sum += list.get(i);
            if(sum > bricks)
                return false;
        }
        return true;
    }
}
